# 83/100 动态规划-打家劫舍
# leetcode第198题: https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/7
from leetcode import test


def rob(nums: list[int]) -> int:
    n = len(nums)
    if n < 2:
        return nums[0]
    if n == 2:
        return max(nums)

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[1], nums[0])
    res = 0
    for i in range(2, n):
        dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
        res = max(res, dp[i])
    return res


if __name__ == '__main__':
    inp = [{"nums": [1, 2, 3, 1]}, {"nums": [2, 7, 9, 3, 1]}, {"nums": [7, 1, 3, 1000]},
           {"nums": [2, 1, 1, 2]}]
    out = [4, 12, 1007, 4]

    test.test_function(rob, inp, out)
